package offer.offer04;

import java.util.Arrays;

/**
 * 不能用除法那就构建从前往后和从后往前两个序列, 然后把两个序列中对应的相乘了。
 */
public class Solution66 {
    public int[] constructArr(int[] a) {
        if(a == null || a.length == 0) return new int[0];
        if(a.length == 1) return a;
        int aLen = a.length;
        int[] leftArray = new int[aLen];
        int[] rightArray = new int[aLen];
        //左序列
        leftArray[0] = 1;
        leftArray[1] = a[0];
        for(int i = 2; i < aLen; i++){
            leftArray[i] = leftArray[i - 1]*a[i - 1];
        }
        System.out.println("leftArray: " + Arrays.toString(leftArray));
        //右序列
        rightArray[0] = 1;
        rightArray[1] = a[aLen - 1];
        for(int i = 2; i < aLen; i++){
            rightArray[i] = rightArray[i - 1]*a[aLen - i];
        }
        System.out.println("rightArray: " + Arrays.toString(rightArray));
        //result
        int[] result = new int[aLen];
        for(int i = 0; i < aLen; i++){
            result[i] = leftArray[i] * rightArray[aLen - i - 1];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] input = new int[]{1, 2, 0, 4, 5};
        System.out.println("result: " + Arrays.toString(new Solution66().constructArr(input)));
    }
}
